#include "algorithm_tabu.h"

/** Urcuje zda je dany pohyb tabu. Pohyb je tabu, pokud danemu vysilaci byla v poslednich
 * tazich prirazena nova frekvence, nebo pokud byl vysilac prilis menen v cele historii.
 * \param antena meneny vysilac
 * \param frequency nova frekvence
 * \return true, pokud je pohyb tabu
 */
bool TabuHistory::IsTabu(int antena, int frequency) {
	/* if I changed the current antena too frequently or assigned the same frequency 
		in last (length) moves, it is a taboo */
	if ((double)(history[antena].size()) / round > rate) {
		return true;
	}
	for (HistoryIterator i = history[antena].begin(); i != history[antena].end(); ++i) {
		if (i->first >= (round - length) && i->second == frequency) {
			return true;
		}
	}
	return false;
}

/** Prida pohyb do historie pohybu.
 * \param antena zmeneny vysilac
 * \param frequency jeho nova frekvence
 */
void TabuHistory::Add(int antena, int frequency) {
	history[antena].push_back(std::pair<int, int>(round, frequency));
	++round;
}

/** Vycisti celou historii.
 */
void TabuHistory::Clear() {
	for (int i = 0; i < size; ++i) {
		history[i].clear();
	}
	round = 1;
	energy = MAXINT;
}

/** Spocte energii reseni dosazeneho danou zmenou.
 * \param change zmena aktualniho reseni
 */
void TabuSolution::CountEnergy(TabuChange &change) {
	change.energy = Energy();
	/* subtract the constraints made by the changed antena and add the new ones */
	int cell = area->findCell(change.antena);
	for (std::vector<int>::const_iterator n = area->cells[cell].constraints.begin();
		n != area->cells[cell].constraints.end(); ++n) {
		/* all neighbours' calls */
		int distance = area->frequencyDistance(cell, *n);
		for (int call = area->cells[*n].index; call < area->cells[*n].index + area->cells[*n].demand; ++call) {
			if (call == change.antena) continue;
			if (abs(area->calls[change.antena] - area->calls[call]) < distance) {
				change.energy -= distance - abs(area->calls[change.antena] - area->calls[call]);
			}
			if (abs(change.frequency - area->calls[call]) < distance) {
				change.energy += distance - abs(change.frequency - area->calls[call]);
			}
		}
	}
}

/** Snizi pocet pouzitelnych frekvenci. Vsechny vysilace, kterym byla nejvetsi frekvence prirazen jsou
 * preladeny na nahodnou nizsi frekvenci.
 * \param frequencies hodnota odebirane frekvence, vystupni parametr, nakonec je zmensena o 1
 */
void TabuSolution::LowerFrequencies(int & frequencies) {
	energy = 0;
	TabuChange change;
	/* mark and reassign the ones with the highest frequency */
	for (int i = 0; i < area->size; ++i) {
		if (area->calls[i] == frequencies) {
			change.antena = i;
			change.frequency = (rand() % (frequencies - 1)) + 1; // assign new random frequency [1..frequencies-1]
			CountEnergy(change);
			area->calls[i] = change.frequency;
			energy = change.energy;
		}
	}
//	options->Log() << "E po snizeni Freq: " << energy << std::endl;
	/* count the energy of the system and lower the number of the frequencies */
	UpdateViolations();
	--frequencies;
}

/** Upravi seznam porusujicich vysilacu i masku poruseni. Automaticky volane po zmene aktualniho reseni.
 */
void TabuSolution::UpdateViolations() {
	count = 0;
	/* mark as violating all the antenas, that violate any constration (are too close) */
	for (int i = 0; i < area->size; ++i) {
		bool violates = false;
		int cell = area->findCell(i);
		/* all neighbours */
		for (std::vector<int>::const_iterator n = area->cells[cell].constraints.begin();
			n != area->cells[cell].constraints.end(); ++n) {
			/* all neighbours' calls */
			int distance = area->frequencyDistance(cell, *n);
			for (int call = area->cells[*n].index; call < area->cells[*n].index + area->cells[*n].demand; ++call) {
				if (call == i) continue;
				if (abs(area->calls[i] - area->calls[call]) < distance) {
					violates = true;
					break;
				}
			}
		}
		if (violates) {
			violating[count++] = i;
		}
	}
}

/** Provede danou zmenu s aktualnim resenim.
 * \param change zmena reseni
 */
void TabuSolution::MoveTo(TabuChange & change) {
	area->calls[change.antena] = change.frequency;
	history.Add(change.antena, change.frequency);
	history.RoundEnergy(change.energy);
	/* recount the violation mask */
	energy = change.energy;
	UpdateViolations();
}

/** Najde nejlepsi reseni v sousedstvi a prejde do nej.
 */
void TabuRandomSolution::MoveToBest() {
	/* choose the best of all neighbours - according to history (tabu...) */
	TabuChange best, best_tabu;
	bool found = false;
	for (int i = 0; i < area->size; ++i) {
		if ((neighbours[i].energy < best.energy)) {
			if (!history.IsTabu(neighbours[i].antena, neighbours[i].frequency)) {
				best = neighbours[i];
			}
			else {
				best_tabu = neighbours[i];
			}
		}
	}
	// perform a tabu move, if it leads to best situation in a history or if there are only tabu moves
	if (best_tabu.energy < best.energy && (best_tabu.energy < history.MinEnergy() || best.energy == MAXINT)) {
		options->Log() << "T ";
		best = best_tabu;
	}

	MoveTo(best);
/*	if (best.energy > 100) {
		options->Log() << "VELKA";
	}*/
//	options->Log() << " presouvam se na: " << best.energy << " (" << best.antena << " = " << best.frequency << ")";
}

/** Vygeneruje cele omezene nahodne sousedstvi.
 * \param frequencies pocet pouzitelnych frekvenci
 */
void TabuRandomSolution::GetNeighbours(int frequencies) {
	for (int i = 0; i < area->size; ++i) {
		/* choose a random violating call */
		neighbours[i].antena = violating[rand() % count];
		/* assign it to a different frequency */
		do {
			neighbours[i].frequency = rand() % frequencies + 1;
		} while (neighbours[i].frequency == area->calls[neighbours[i].antena]);
		CountEnergy(neighbours[i]);
	}
}

/** Spusti algoritmus tabu search na vyreseni zadane mapy.
 * Nejprve vytvori prvotni prirazeni podle zadaneho prvotniho algoritmu, pote vzdy odebere nejvyssi
 * frekvenci a v takovemto reseni se snazi minimalizovat energii na 0 pomoci algoritmu tabu search.
 * \return true, pokud se povedlo vytvorit korektni prirazeni frekvenci 
 */
bool TabuAlgorithm::Solve() {
	timer->start();
	/* run initial assignment algorithm (specified as my son) */
	Algorithm * initial = TestManager::GetAlgorithm(options->initial, options);
	if (!initial) {
		options->Log() << "Error: invalid initial algorithm!" << std::endl;
		return false;
	}
	initial->Set(area);
	if (!initial->Solve()) {
		options->Log() << "Error: initial algorithm assigned a bad assignment!" << std::endl;
		delete initial;
		return false;
	}
	options->Log() << "- initial algorithm (" << initial->GetDetail() << ") assigned: " << initial->Frequencies() << " frequencies in " << timer->lap() << " s." << std::endl
		<< "- starting tabu search for optimalization of the solution" << std::endl;
	frequencies = initial->Frequencies() + 1;
	delete initial;

	/* try to optimise it as much as I can
		- take out the highest frequency
		- run simulated annealing to assign the frequencies lower frequencies to them
	*/
	TabuSolution * solution;
	solution = new TabuRandomSolution(area, options);
	// write out some text
	options->NewDisplay();
	options->Display(", Tabu: ");
	options->NewDisplay();
	options->Log() << "Frequency;Violations;;Energies;" << std::endl;
	while (solution->Energy() == 0) {
		/* reassign antenas with the highest frequency to a randomly chosen lower one
			and mark the antenas violating any of the constraint
			and count the energy of the system
		*/
		area->save();
		solution->ClearHistory();
		solution->LowerFrequencies(frequencies);
		// options->Log() << "Pokus o snizeni frekvenci na: " << Frequencies() << ", energie: " << solution->Energy() << ", pocet porusujicich: " << solution->ViolatingCount() << ", cas: " << timer->lap() << std::endl;
		/* create 0 constraint violation assignment */
		options->Log() << Frequencies() << ";" << solution->ViolatingCount() << ";;" << solution->Energy() << ";";
		while ((solution->Energy() != 0) && (solution->LoopNumber() < options->loop_count)) {
			// try to reassign frequencies and have no constraints broken
			solution->GetNeighbours(frequencies);
			solution->MoveToBest();
			options->Log() << solution->Energy() << ";";
			options->Display(IntToStr(frequencies) + ", E = " + IntToStr(solution->Energy()));
		}
		options->Log() << std::endl;
	}
	++frequencies; // last time it did not produce 0 energy
	area->load();
	options->Log() << "Tabu search dopocital za " << timer->total() << std::endl;
	return true;
}
